#include"main.h"
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
//创建二叉树函数
void create_tree(BiTreeNode **root_pp,char *pre_order_seq,int num_elements) {
    //使用静态变量或临时变量跟踪索引
    static int index = 0;

    //如果当前索引大于或等于元素数量，返回
    if(index >= num_elements) {
        return;
    }
    //如果遇到‘#’,表示空指针
    if(pre_order_seq[index] == '#') {
        (*root_pp) = NULL;
        index++;
        return;
    }

    //创建新的节点
    *root_pp = (BiTreeNode *)malloc(sizeof(BiTreeNode));
    if(*root_pp == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }

    //赋值数据域
    (*root_pp)->data = pre_order_seq[index];
    index++;

    //递归创建左子树和右子树
    create_tree(&(*root_pp)->leftChild, pre_order_seq, num_elements);
    create_tree(&(*root_pp)->rightChild, pre_order_seq, num_elements);
}

//前序遍历
void pre_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if(t != NULL) {
        visit(t->data);//访问跟节点
        pre_order_traverse(t->leftChild, visit);//左子树
        pre_order_traverse(t->rightChild, visit);//右子树
    }
}

//中序遍历
void in_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if(t != NULL) {
        in_order_traverse(t->leftChild, visit);
        visit(t->data);
        in_order_traverse(t->rightChild, visit);
    }
}

//后序遍历
void post_order_traverse(BiTreeNode *t, void visit(DataType item)) {
    if(t != NULL) {
        post_order_traverse(t->leftChild, visit);
        post_order_traverse(t->rightChild, visit);
        visit(t->data);
    }
}

//查找元素值
BiTreeNode *search(BiTreeNode *root, DataType x) {
    if(root == NULL) {
        return NULL;//如果树为空，返回NULL
    }
    //如果找到x,返回节点
    if (root->data == x) {
        return root;
    }

    //在左子树中查找
    BiTreeNode *left_result = search(root->leftChild, x);
    if(left_result != NULL) {
        return left_result;
    }

    //再右子树中查找
    return search(root->rightChild, x);
}

//访问函数
void Visit(DataType item) {
    printf("%c",item);
}

//销毁二叉树
void destroy(BiTreeNode **root) {
    if(*root != NULL) {
        destroy(&(*root)->leftChild);//销毁左子树
        destroy(&(*root)->rightChild);//销毁右子树
        free(*root);//释放根节点
        *root = NULL;//清空指针
    }
}

//主函数
int main() {
    char *pre_order_seq = "ABC##DE#G##F###";
    BiTreeNode *root = NULL;

    //获取元素数量
    int num_elements = strlen(pre_order_seq);//获取字符串的长度
    int index = 0;

    //创建二叉树
    create_tree(&root, pre_order_seq,num_elements);

    //前序遍历
    printf("前序遍历: ");
    pre_order_traverse(root, Visit);
    printf("\n");

    //中序遍历
    printf("中序遍历: ");
    in_order_traverse(root, Visit);
    printf("\n");

    //后序遍历
    printf("后序遍历: ");
    post_order_traverse(root, Visit);
    printf("\n");

    //销毁二叉树
    destroy(&root);

    return 0;
}